from typing import List
import heapq
from collections import  defaultdict


def network_flow(nodes: List[int], edges_: List[List[int]]):
    n = len(nodes)
    inf = 10 ** 15
    edges = defaultdict(list)
    for a, b, d in edges_:
        edges[a].append([b, d])
        edges[b].append([a, d])

    def dijkstra(s, t):
        distances = [inf] * (n + 1)
        distances[s] = 0
        q = [(distances[s], s)]
        while q:
            du, u = heapq.heappop(q)
            if du > distances[u]:
                continue
            if u == t or du >= distances[t]:
                break
            for v, duv in edges[u]:
                opt = du + duv
                if opt < distances[v]:
                    distances[v] = opt
                    heapq.heappush(q, (opt, v))
        return distances

    forward_d = dijkstra(1, n)
    backward_d = dijkstra(n, 1)
    shortest_length = forward_d[n]

    def get_paths():
        paths = []
        stack = []

        def dfs_visit(u):
            stack.append(u)
            if u == n:
                paths.append(stack.copy())
            else:
                for v, duv in edges[u]:
                    if forward_d[u] + duv + backward_d[v] == shortest_length:
                        dfs_visit(v)
            stack.pop()
        dfs_visit(1)
        return paths

    result = 0
    capacities = [inf] + nodes
    capacities[1] = capacities[n] = inf
    paths = get_paths()
    for path in paths:
        cap = min(capacities[v] for v in path)
        for v in path:
            capacities[v] -= cap
        result += cap
    return result


nodes = [1, 100, 20, 50, 20, 60, 1]
edges = [[1,2,2], [1,5,2], [2,4,1],[2,3,3],[3,7,1],[4,5,4],[4,3,1],[4,6,1],[5,6,2],[6,7,1]]
res = network_flow(nodes, edges)
print(res)
